1352. Сумма простых чисел

Вася полюбил простые числа. Он решил найти такую сумму n первых простых чисел, которая будет делится нацело на число k. Помогите ему.

Вход. Одно число k (1 ≤ k ≤ 1000).

Выход. Выведите наименьшее возможное число n.

Пример входа	Пример выхода
7	5

РЕШЕНИЕ

простые числа

Анализ алгоритма

Перебираем первые простые числа (2, 3, 5, 7, …), суммируем их. Как только сумма будет делиться на k, выводим количество использованных слагаемых.

Пример

Сумма первых пяти простых чисел 2 + 3 + 5 + 7 + 11 = 28 делится на 7.

Реализация алгоритма

Функция prime возвращает 1, если число n является простым.

int prime(int n)

{

if (n == 2) return 1;

if (n % 2 == 0) return 0;

for(int i = 3; i <= sqrt(n); i += 2)

if(n % i == 0) return 0;

return 1;

}

Основная часть программы. Читаем значение k.

scanf("%d",&k);

В переменной s подсчитываем сумму простых чисел, в переменной c их количество.

s = c = 0;

Перебираем числа, начиная с 2. Если число простое, то прибавляем его к s. Как только сумма s будет делиться на k, останавливаемся.

for(i = 2;; i++)

{

if (prime(i))

{

s += i; c++;

if (s % k == 0) break;

}

}

Выводим наименьшее количество первых простых чисел, сумма которых делится на k.

printf("%d\n",c);

Java реализация

import java.util.*;

public class Main

{

public static boolean prime(int n)

{

if (n == 2) return true;

if (n % 2 == 0) return false;

for(int i = 3; i <= Math.sqrt(n); i += 2)

if(n % i == 0) return false;

return true;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int k = con.nextInt();

int s = 0, c = 0;

for(int i = 2;; i++)

{

if (prime(i))

{

s += i; c++;

if (s % k == 0) break;

}

}

System.out.println(c);

con.close();

}

}

Python реализация

import math

def prime(n):

if n == 2: return True

if n % 2 == 0: return False

for i in range(3, int(math.sqrt(n))+1, 2):

if n % i == 0: return False

return True

k = int(input())

s = c = 0

i = 2

while True:

if (prime(i)):

s += i

c += 1

if s % k == 0: break

i += 1

print(c);